UVa/12320 - Flight Control/12320.5.cpp

   1 // Ternary search and binary search. Accepted.
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <numeric>
   7 #include <sstream>
   8 #include <fstream>
   9 #include <cassert>
  10 #include <climits>
  11 #include <cstdlib>
  12 #include <cstring>
  13 #include <string>
  14 #include <cstdio>
  15 #include <vector>
  16 #include <cmath>
  17 #include <queue>
  18 #include <deque>
  19 #include <stack>
  20 #include <list>
  21 #include <map>
  22 #include <set>
  23
  24 template <class T> string toStr(const T &x) { stringstream s; s << x; return s.str(); }
  25 template <class T> int toInt(const T &x) { stringstream s; s << x; int r; s >> r; return r; }
  26
  27 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  28 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
  29 #define D(x) cout << #x " = " << (x) << endl
  30
  31 namespace IO {
  32 #define MAXBUFF (1<<20)
  33    char buffer[MAXBUFF], *p = buffer+MAXBUFF;
  34    char buffer2[MAXBUFF], *p2 = buffer2;
  35
  36    inline char read_char() {
  37       if( p == buffer+MAXBUFF ) {
  38          fread( buffer, 1, MAXBUFF, stdin );
  39          p = buffer;
  40       }
  41       return *p++;
  42    }
  43
  44    inline int read_int() {
  45       char c = read_char();
  46       while( !isdigit(c) and c != '-' ) c = read_char();
  47       int sign = c == '-' ? -1 : +1;
  48       if (c == '-') c = read_char();
  49       int ret = c-'0';
  50       while( isdigit(c = read_char()) ) ret = ret * 10 + c-'0';
  51       return ret * sign;
  52    }
  53
  54    void flush() {
  55       fwrite( buffer2, 1, p2-buffer2, stdout );
  56       p2 = buffer2;
  57    }
  58
  59    inline void write( char c ) {
  60       if( p2 == buffer2+MAXBUFF ) {
  61          fwrite( buffer2, 1, MAXBUFF, stdout );
  62          p2 = buffer2;
  63       }
  64       *p2++ = c;
  65    }
  66 }
  67
  68 const double EPS = 1e-10;
  69
  70 int cmp(double x, double y = 0, double tol = EPS){
  71     return( x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
  72 }
  73
  74 struct point {
  75     double x, y, z;
  76     point(){} point(double x, double y, double z) : x(x), y(y), z(z) {}
  77 };
  78
  79 int R[2], V[2];
  80 vector< point > P[2];
  81 double D[2][105];
  82
  83 inline double dist(const point &a, const point &b) {
  84     double dx = b.x - a.x, dy = b.y - a.y, dz = b.z - a.z;
  85     return sqrt(dx * dx + dy * dy + dz * dz);
  86 }
  87
  88 point positionAt(int p, double t) {
  89     double d = V[p] * t;
  90
  91     int i = upper_bound(D[p], D[p] + P[p].size(), d) - D[p] - 1;
  92     assert(i >= 0);
  93     double s = D[p][i];
  94     double distance = dist(P[p][i], P[p][i+1]);
  95     //assert(cmp(s + distance, d) >= 0);
  96     point ans = P[p][i];
  97     if (cmp(distance, 0.0) > 0) {
  98         double dx = P[p][i+1].x - P[p][i].x;
  99         double dy = P[p][i+1].y - P[p][i].y;
 100         double dz = P[p][i+1].z - P[p][i].z;
 101         ans.x += (d - s) * dx / distance;
 102         ans.y += (d - s) * dy / distance;
 103         ans.z += (d - s) * dz / distance;
 104     }
 105     //assert(cmp(s + dist(P[p][i], ans), d) == 0);
 106     return ans;
 107 }
 108
 109 double distanceAtTime(double t) {
 110     point p0 = positionAt(0, t);
 111     point p1 = positionAt(1, t);
 112     return dist(p0, p1);
 113 }
 114
 115 double touchAtTime(double t) {
 116     return cmp(distanceAtTime(t), 0.0 + R[0] + R[1]) <= 0;
 117 }
 118
 119 double findClosestTime(double left, double right) {
 120     // double bestTime = -1, bestDistance = 1e200;
 121     // for (double t = left; t <= right; t += 0.5) {
 122     //     double d = distanceAtTime(t);
 123     //     printf("At time %lf, distance is %lf\n", t, d);
 124     //     if (cmp(d, bestDistance) < 0) {
 125     //         bestDistance = d;
 126     //         bestTime = t;
 127     //     }
 128     // }
 129
 130     while (cmp(left, right) < 0) {
 131         double t1 = (2 * left + right) / 3;
 132         double t2 = (2 * right + left) / 3;
 133         double d1 = distanceAtTime(t1);
 134         double d2 = distanceAtTime(t2);
 135         if (d1 > d2) {
 136             left = t1;
 137         } else {
 138             right = t2;
 139         }
 140     }
 141     double ans = (left + right) / 2;
 142     //printf("Best is at time %lf, where distance is %lf\n", ans, distanceAtTime(ans));
 143     return ans;
 144 }
 145
 146 int main(){
 147     int casos = IO::read_int(); while (casos--) {
 148         for (int p = 0; p < 2; ++p) {
 149             int k;
 150             R[p] = IO::read_int(), V[p] = IO::read_int(), k = IO::read_int();
 151             P[p].resize(k);
 152             for (int i = 0; i < k; ++i) {
 153                 P[p][i].x = IO::read_int(), P[p][i].y = IO::read_int(), P[p][i].z = IO::read_int();
 154             }
 155             P[p].push_back( point(0, 0, 0) );
 156         }
 157
 158         double totalTime = 1e100;
 159         for (int p = 0; p < 2; ++p) {
 160             D[p][0] = 0.0;
 161             for (int i = 1; i < P[p].size(); ++i) {
 162                 D[p][i] = D[p][i-1] + dist(P[p][i-1], P[p][i]);
 163             }
 164             totalTime = min(totalTime, D[p][P[p].size() - 1] / V[p]);
 165         }
 166         // D(totalTime);
 167         // point p1 = positionAt(0, totalTime);
 168         // point p2 = positionAt(1, totalTime);
 169         // printf("<%lf, %lf, %lf>\n", p1.x, p1.y, p1.z);
 170         // printf("<%lf, %lf, %lf>\n", p2.x, p2.y, p2.z);
 171         vector<double> times;
 172         for (int p = 0; p < 2; ++p) {
 173             double d = 0;
 174             times.push_back(0.0);
 175             for (int i = 0; i < P[p].size() - 1; ++i) {
 176                 d += dist(P[p][i], P[p][i+1]);
 177                 double t = d / V[p];
 178                 if (cmp(t, totalTime) <= 0) times.push_back(d / V[p]);
 179             }
 180         }
 181         sort(times.begin(), times.end());
 182         //For(i, 0, times.size() - 1) assert(cmp(times[i], times[i + 1]) <= 0);
 183         // for (int i = 0; i < times.size(); ++i) {
 184         //     printf("%lf ", times[i]);
 185         // }
 186         // puts("");
 187
 188         int ans = 0;
 189         for (int i = 0; i < times.size() - 1; ++i) {
 190             //printf("\nInterval from time (%lf, %lf):\n", times[i], times[i+1]);
 191             const double &t = times[i];
 192             if (touchAtTime(t)) {
 193                 //printf("They touch at time %lf, continuing.\n", t);
 194                 continue;
 195             }
 196             double closestTime = findClosestTime(t, times[i+1]);
 197             if (touchAtTime(closestTime)) {
 198                 ans++;
 199             }
 200         }
 201         if (touchAtTime(0.0)) ans++;
 202         printf("%d\n", ans);
 203     }
 204     return 0;
 205 }